package synchronicity.util;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.util.Vector;

import synchronicity.io.Streamable;

/**
 * A set of noncontiguous, continuous, and inclusive ranges that do not overlap.
 * This set is kept in order at all times by using a weird form of insertion
 * sort.
 */
public class RangeSet implements Streamable {
	Vector ranges;

	public RangeSet() {
		ranges = new Vector();
	}

	public void addRange(long left, long right) {
		addRange(new Range(left, right));
	}

	public synchronized void addRange(Range rangeToAdd) {
		if (ranges.size() > 0) {
			Range current;

			for (int ii = 0; ii < ranges.size(); ii++) {
				current = (Range) ranges.elementAt(ii);
				if (rangeToAdd.compareTo(current) == 0) {
					// We encountered an intersecting range, so
					// start merging from this element on.
					mergeAllEqualRanges(rangeToAdd, ii);
					break;
				} else if (rangeToAdd.compareTo(current) < 0) {
					ranges.insertElementAt(rangeToAdd, ii);
					break;
				} else if (ii == ranges.size() - 1) {
					// insert at end
					ranges.addElement(rangeToAdd);
					break;
				}
			}
		} else {
			ranges.addElement(rangeToAdd);
		}
	}

	private void mergeAllEqualRanges(Range rangeToAdd, int startIndex) {
		int endIndex = startIndex;
		Range merged = rangeToAdd;
		for (int ii = startIndex; ii < ranges.size(); ii++) {
			Range currentRange = (Range) ranges.elementAt(ii);
			if (currentRange.compareTo(rangeToAdd) == 0) {
				endIndex = ii;
				merged = currentRange.union(merged);
			} else {
				break;
			}
		}
		for (int ii = startIndex; ii <= endIndex; ii++) {
			ranges.removeElementAt(startIndex);
		}
		ranges.insertElementAt(merged, startIndex);
	}

	/**
	 * Unions this RangeSet with another.
	 */
	public RangeSet union(RangeSet other) {
		RangeSet result = new RangeSet();
		for (int ii = 0; ii < ranges.size(); ii++)
			result.addRange((Range) ranges.elementAt(ii));
		Vector otherRanges = other.getRanges();
		for (int ii = 0; ii < otherRanges.size(); ii++)
			result.addRange((Range) otherRanges.elementAt(ii));

		return result;
	}

	public boolean equals(Object obj) {
		try {
			RangeSet other = (RangeSet) obj;
			Vector otherRanges = other.getRanges();
			if (otherRanges.size() != getRanges().size())
				return false;
			for (int ii = 0; ii < getRanges().size(); ii++) {
				Range range = (Range) getRanges().elementAt(ii);
				Range otherRange = (Range) otherRanges.elementAt(ii);
				if (!range.equals(otherRange))
					return false;
			}
			return true;
		} catch (ClassCastException cce) {
			return false;
		}
	}

	/**
	 * Find the subset of these ranges in the specified range. Will clip
	 * bordering ranges to match the parameter
	 */
	public RangeSet subset(Range span) {
		RangeSet result = new RangeSet();
		for (int ii = 0; ii < ranges.size(); ii++) {
			Range r = (Range) ranges.elementAt(ii);
			if (r.intersects(span)) {
				result.addRange(span.intersect(r));
			}
		}
		return result;
	}

	public Vector getRanges() {
		return ranges;
	}

	public synchronized void read(DataInputStream stream) throws IOException {
		ranges.removeAllElements();
		int size = stream.readInt();
		for (int ii = 0; ii < size; ii++) {
			Range newRange = new Range(0, 0);
			newRange.read(stream);
			ranges.addElement(newRange);
		}
	}

	public synchronized void write(DataOutputStream stream) throws IOException {
		stream.writeInt(ranges.size());
		for (int ii = 0; ii < ranges.size(); ii++) {
			Range range = (Range) ranges.elementAt(ii);
			range.write(stream);
		}
	}

}
